//
// Created by dengspc on 2019/2/11.
//

#ifndef INC_010_ALGORITHM_BTREE_H
#define INC_010_ALGORITHM_BTREE_H

//https://www.cnblogs.com/lwhkdash/p/5313877.html
//https://blog.csdn.net/u014165620/article/details/82976882
//https://www.cs.usfca.edu/~galles/visualization/BTree.html 演示网站

/**
 * 具体讲解之前，有一点，再次强调下：B-树，即为B树。因为B树的原英文名称为B-tree，
 * 而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。
 * 如人们可能会以为B-树是一种树，而B树又是一种一种树。而事实上是，B-tree就是指的B树。特此说明。
 *
 * B 树又叫平衡多路查找树。一棵m阶的B 树 (m叉树)的特性如下：
 * 树中每个结点最多含有m个孩子（m>=2）；
 * 除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数）；
 * 若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；
 * 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；（读者反馈@冷岳：这里有错，叶子节点只是没有孩子和指向孩子的指针，这些节点也存在，也有元素。@JULY：其实，关键是把什么当做叶子结点，因为如红黑树中，每一个NULL指针即当做叶子结点，只是没画出来而已）。
 * 每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：
       a)   Ki (i=1...n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。
       b)   Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。
       c)   关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。如下图所示：

 * B+-tree：是应文件系统所需而产生的一种B-tree的变形树。
 * 一棵m阶的B+树和m阶的B树的差异在于：
 *     1.有n棵子树的结点中含有n个关键字； (而B 树是n棵子树有n-1个关键字)
 *       2.所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，
 *       且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)
 *       3.所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。
 *       (而B 树的非终节点也包含需要查找的有效信息)
 *
 *
 *  B*-tree是B+-tree的变体，在B+ 树非根和非叶子结点再增加指向兄弟的指针；
 *  B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）
 *
 */

#endif //INC_010_ALGORITHM_BTREE_H
